home *** CD-ROM | disk | FTP | other *** search
/ BCI NET 2 / BCI NET 2.iso / archives / diskmags / shoah_s_iss1.lha / source / Shellsort.s < prev    next >
Encoding:
Text File  |  1991-06-13  |  12.2 KB  |  487 lines
  1. ;      _______  ___                    ___        _______
  2. ;     /°-     \/. /    _____   ____   / ./       /°-     \
  3. ;     \   \___//  \___/°    \_/°   \_/   \___    \   \___/
  4. ;    _/\__    \      ~\_  /\  \  /\ ~\      °\_ _/\__    \
  5. ;    \\       /   /\   /  \/. /  \/   \ //\   / \\       /
  6. ;     \______/\__/  \_/\_____/\____/\_/_/  \_/ o \______/ Issue 1
  7.  
  8. ;i used asmone and trashemone
  9. ;*****************************************************************************
  10. ;exec.library
  11. allocmem    equ    -198
  12. freemem        equ    -210
  13. oldopenlibrary    equ    -408
  14. closelibrary    equ    -414
  15.  
  16. ;dos.library
  17. open        equ    -30
  18. close        equ    -36
  19. read        equ    -42
  20. write        equ    -48
  21. output        equ    -60
  22. lock        equ    -84
  23. unlock        equ    -90
  24. examine        equ    -102
  25.  
  26.  
  27.     movem.l    d1-d7/a1-a6,-(a7)    ;store regs
  28. ;-------------
  29.     move.l    $4.w,a6
  30.     movem.l    d0/a0,-(a7)        ;store temporary
  31.     lea    doslib,a1
  32.     jsr    oldopenlibrary(a6)
  33.     move.l    d0,a5
  34.     movem.l    (a7)+,d0/a0        ;regs back
  35.     move.l    a5,dosbase        ;store dos base
  36.  
  37.     cmp.l    #1,d0            ;if there is no input from CLI
  38.     beq.w    kraj            ;go to end
  39.     cmp.b    #$3f,(a0)        ;is first character '?'
  40.     beq.w    kraj
  41.     
  42.     move.l    a0,a2            ;store address of CLI input 
  43.     lea    buff,a1
  44.     bsr.w    string            ;read one text word
  45.     cmp.b    #"-",(a1)
  46.     bne.b    nista
  47.     move.b    #$ff,flag        ;set only flag for option '-n'
  48.     bra.b    nesta
  49. nista    move.b    #0,flag            ;reset flag
  50.     move.l    a2,a0            ;no options, bring back
  51. nesta    lea    ulaz,a1
  52.     bsr.w    string            ;read input file name
  53.     lea    izlaz,a1
  54.     bsr.w    string            ;read output file name
  55. ;***********************************************************************
  56.     jsr    output(a5)        ;take handle pointer
  57.     move.l    d0,d1
  58.     move.l    #reading,d2
  59.     moveq    #$0b,d3
  60.     jsr    write(a5)        ;write text "reading..."
  61.  
  62.     move.l    #$108,d0        ;264 bytes for FileInfoBlock
  63.     moveq    #00,d1
  64.     jsr    allocmem(a6)
  65.     move.l    d0,a4            ;store temporary
  66.  
  67.     move.l    #ulaz,d1
  68.     move.l    #-2,d2            ;shared lock
  69.     jsr    lock(a5)        ;lock
  70.  
  71.     tst.l    d0
  72.     beq.w    error1
  73.  
  74.     move.l    d0,-(a7)        ;store pointer
  75.     move.l    d0,d1            ;lock pointer
  76.     move.l    a4,d2            ;FileInfoBlock allocation
  77.     jsr    examine(a5)        ;examine file
  78.  
  79.     tst.l    d0
  80.     beq.w    error1
  81.     move.l    $7c(a4),size        ;store file length
  82.  
  83.     move.l    #$108,d0
  84.     move.l    a4,a1
  85.     jsr    freemem(a6)        ;free 264 bytes
  86.  
  87.     move.l    (a7)+,d1        ;take back lock pointer
  88.     jsr    unlock(a5)        ;unlock
  89. ;-------------
  90.     move.l    size,d0
  91.     moveq    #00,d1
  92.     jsr    allocmem(a6)        ;alocate place for input file
  93.  
  94.     move.l    d0,a4            ;store pointer
  95.     move.l    d0,source
  96.     move.l    size,d0
  97.     moveq    #00,d1
  98.     jsr    allocmem(a6)        ;alocate place for sorted file
  99.  
  100.     move.l    d0,dest            ;store pointer
  101. ;-------------
  102.     move.l    #ulaz,d1
  103.     move.l    #1005,d2
  104.     jsr    open(a5)        ;open input file
  105.  
  106.     tst.l    d0
  107.     beq.w    error1            ;on error, finish
  108.     move.l    d0,-(a7)        ;store file pointer
  109.  
  110.     move.l    d0,d1
  111.     move.l    a4,d2
  112.     move.l    size,d3
  113.     jsr    read(a5)        ;read input file
  114.  
  115.     tst.l    d0
  116.     beq.w    error1
  117.     move.l    d0,length        ;store number of bytes readed
  118.  
  119.     move.l    (a7)+,d1        ;take back file pointer
  120.     jsr    close(a5)        ;close input file
  121. ;*************************************************************************
  122.     clr.l    d5            ;lines counter
  123.     tst.b    flag            ;do we have option '-n'
  124.     bne.b    bb
  125.  
  126.     move.l    length,d0        ;read file length
  127.     moveq    #10,d3            ;LINE FEED
  128.     bra.b    ba
  129.  
  130. ba0    addq.l    #1,d5            ;lines counter++
  131. ba     subq.l    #1,d0            ;char counter--
  132.     tst.l    d0
  133.     bmi.b    otislo            ;have we read all chars
  134.     cmp.b    (a4)+,d3        ;is char LINE FEED
  135.     bne.b    ba            ;jump if not LF
  136.  
  137.     bra.b    ba0
  138. ;-------------
  139. bb    move.l    length,d0        ;read file length
  140.     moveq    #0,d2            ;clear counter (no. of chars in line)
  141.     moveq    #$0a,d3            ;LINE FEED
  142.     moveq    #$20,d1            ;SPACE
  143.     moveq    #01,d7
  144.     bra.b    b21
  145.  
  146. b11    subq.l    #1,d0            ;char counter--
  147.     addq.l    #1,a4            ;address++
  148.     tst.l    d0            ;is it end of file
  149.     bmi.b    otislo            ;if it is, go further
  150.  
  151. b21    cmp.b    (a4),d1            ;is char less than SPACE
  152.     bge.b    b11            ;it is, jump (SPACE is > than char)
  153.  
  154. bc     subq.l    #1,d0            ;char counter--
  155.     tst.l    d0
  156.     bmi.b    otislo
  157.     addq.b    #1,d2            ;chars in line counter++
  158.     cmp.b    (a4)+,d3        ;is it LINE FEED(end of line)
  159.     bne.b    bc            ;jump if not LF
  160.  
  161.     cmp.b    d7,d2            ;is line length 1 (only LF)
  162.     beq.b    bd            ;if it is, ignore it
  163.     addq.l    #1,d5            ;lines counter++
  164. bd    moveq    #0,d2            ;clear counter
  165.     bra.b    b21
  166. ;-------------
  167. otislo    move.l    d5,no_of_lines        ;store it
  168.     
  169.     move.l    d5,d0            ;no. of lines
  170.     lsl.l    #2,d0            ;divide by 4
  171.     addq.l    #4,d0            ;add 4 bytes
  172.     move.l    d0,size2
  173.     moveq    #00,d1
  174.     jsr    allocmem(a6)        ;alocate place for pointers on
  175.                     ;beginning of line
  176.     move.l    d0,a3            ;store pointer
  177.     move.l    d0,pointers1
  178.     move.l    source,a4
  179.     
  180.     tst.b    flag            ;check option
  181.     bne.b    aa
  182.     move.l    a4,(a3)+        ;first pointer is pointer on
  183.                     ;   first char in file 
  184. aa    move.l    no_of_lines,d0
  185.     moveq    #00,d1            ;alocate place for lenghts
  186.     jsr    allocmem(a6)        ;of lines
  187.  
  188.     move.l    d0,pointers2
  189. ;-------------
  190.     tst.b    flag            ;test flag
  191.     bne.w    read2
  192.  
  193.     move.l    length,d0        ;take file length
  194.     move.l    pointers2,a2        ;place for line pointers
  195.     moveq    #10,d3            ;LINE FEED
  196.     moveq    #0,d2            ;clear
  197.     bra.b    nije
  198.  
  199. ni    move.b    d2,(a2)+        ;store no of chars in line
  200.     move.l    a4,(a3)+        ;store next address as pointer
  201.     moveq    #0,d2            ;clear counter
  202.  
  203. nije     subq.l    #1,d0            ;char counter--
  204.     tst.l    d0            ;is it all ?
  205.     bmi.b    nema            ;if yes, finish this part
  206.     addq.b    #1,d2            ;chars in line counter++
  207.     cmp.b    (a4)+,d3        ;is it LINE FEED
  208.     bne.b    nije            ;jump if not LF
  209.  
  210.     bra.b    ni
  211. ;-------------
  212. read2    move.l    length,d0        ;take file length
  213.     move.l    d0,d5
  214.     move.l    pointers2,a2        ;place for line pointers
  215.     moveq    #0,d2            ;clear counter
  216.     moveq    #10,d3            ;LINE FEED
  217.     moveq    #32,d1            ;SPACE
  218.     moveq    #01,d7
  219.     bra.b    b2
  220.  
  221. era    moveq    #0,d2            ;clear counter
  222.     subq.l    #1,d5            ;char counter--
  223.     bra.b    b2
  224.         
  225. b1    subq.l    #1,d0            ;char counter--
  226.     tst.l    d0
  227.     bmi.b    nema2            ;is it EOF (jump if is)
  228.     addq.l    #1,a4            ;address++
  229.     subq.l    #1,d5            ;char counter--
  230.  
  231. b2    cmp.b    (a4),d1            ;is it less than SPACE
  232.     bge.b    b1            ;SPACE is greater, jump
  233.  
  234.     move.l    a4,a0            ;store address of line
  235.  
  236. nije2     subq.l    #1,d0            ;char counter--
  237.     tst.l    d0
  238.     bmi.b    nema2            ;is it EOF
  239.     addq.b    #1,d2            ;chars in line counter++
  240.     cmp.b    (a4)+,d3        ;is it LINE FEED (end of line)
  241.     bne.b    nije2            ;jump if not LF
  242.  
  243.     cmp.b    d7,d2            ;is line length 1,only LF
  244.     beq.b    era            ;if is, ignore it
  245.     move.b    d2,(a2)+        ;store no. of chars
  246.     move.l    a0,(a3)+        ;store next address as pointer
  247.     moveq    #0,d2            ;clear counter
  248.     bra.b    b2
  249. nema2    move.l    d5,length        ;store new length of file without
  250.                     ;chars that are ignored
  251. ;**********************************************************************
  252. nema    jsr    output(a5)
  253.     move.l    d0,d1
  254.     move.l    #sorting,d2
  255.     moveq    #$0f,d3
  256.     jsr    write(a5)        ;write text "sorting..."
  257.  
  258.     move.l    no_of_lines,a4        ;read no. of lines
  259.     move.l    a4,d0
  260.         
  261.     move.l    pointers1,a0        ;read address of pointers to source
  262.     move.l    pointers2,a3        ;read address where to put sorted pointers
  263.  
  264.     bra.b    a
  265.  
  266. ;d0=range, d1=i, d2=j, a4=n
  267. ;this variables are same as in algorithm i wrote at start of file
  268. zamjena    move.l    d4,a1            ;get addresses of
  269.     move.l    d5,a2            ;both operands
  270.     move.l    (a2),d4
  271.     move.l    (a1),(a2)        ;first pointer instead second
  272.     move.l    d4,(a1)            ;second pointer instead first
  273.  
  274.     move.l    d6,a1            ;read address of 1st operand
  275.     move.l    d7,a2            ;read address of 2nd operand
  276.     move.b    (a2),d4            ;swap no. of chars in lines
  277.     move.b    (a1),(a2)        ;for same lines as above
  278.     move.b    d4,(a1)
  279.     bra.b    dalje
  280.  
  281. a    lsr.l    #1,d0            ;range divide by 2
  282.     beq.b    gotovo            ;if x==0, finish sort
  283.  
  284.     move.l    d0,d1            ;i=range
  285.     subq.l    #1,d1            
  286.  
  287. b    addq.l    #1,d1            ;i++
  288.     cmp.l    a4,d1            ;is i==n
  289.     beq.b    a            ;if it is, jump
  290.  
  291.     move.l    d1,d2            ;j=i
  292. dalje    sub.l    d0,d2            ;j=i-range
  293.     bmi.b    b            ;if j<0, jump
  294.  
  295.     move.l    a3,d6            ;read addresses of lengths
  296.     add.l    d2,d6            ;   of lines
  297.     move.l    a3,d7            ;for both operands
  298.     add.l    d2,d7
  299.     add.l    d0,d7
  300.  
  301.     asl.l    #2,d2            ;d2=d2*4; for longs
  302.     asl.l    #2,d0            ;d0      -||-
  303.     move.l    a0,a1            ;a1=j-th element
  304.     add.l    d2,a1
  305.     move.l    a0,a2            ;a2=(j+range)-th element
  306.     add.l    d2,a2
  307.     add.l    d0,a2
  308.     move.l    a1,d4            ;store 1st pointer
  309.     move.l    a2,d5            ;store 2nd pointer
  310.     move.l    (a1),a1            ;store 1st operand address
  311.     move.l    (a2),a2            ;store 2nd operand address
  312.     asr.l    #2,d2            ;d2=d2/4
  313.     asr.l    #2,d0            ;d0=d0/4
  314.     
  315. ponovo    cmpm.b    (a1)+,(a2)+        ;compare two chars
  316.     bmi.b    zamjena            ;if 2nd<1st, change them
  317.     beq.b    ponovo            ;if 1st==2nd, check next
  318.     bra.b    b            ;if 1st<2nd, compare next two lines
  319. ;***********************************************************************
  320. gotovo    jsr    output(a5)
  321.     move.l    d0,d1
  322.     move.l    #writing,d2
  323.     moveq    #$0f,d3
  324.     jsr    write(a5)        ;write text "writing..."
  325.  
  326.     move.l    pointers1,a3        ;read start of sorted pointers
  327.     move.l    dest,a2            ;read destination address
  328.     move.l    pointers2,a0        ;read addr. of length of lines
  329.     move.l    no_of_lines,d2        ;read no. of lines
  330.  
  331.     move.b    #$fc,d1            ;mask for savingfirst 6 bits,
  332.                     ;to find no. of longs in line
  333.     moveq    #3,d3            ;3 bytes and  mask %00000011
  334.     moveq    #10,d4            ;LINE FEED    
  335.  
  336. jos    tst.l    d2            ;is lines counter==0
  337.     beq.b    next            ;yes, finish this part
  338.     move.l    (a3)+,a1        ;move pointer of actual line
  339.     subq.l    #1,d2            ;lines counter--
  340.     move.b    (a0)+,d0        ;length of line in bytes
  341.     cmp.b    d3,d0            ;compare with 3
  342.     ble.b    x            ;if length <= 3, jump
  343.  
  344. long    move.b    d0,d6            ;store 
  345.     and.b    d1,d0            ;clear no. of chars with mask %11111100
  346.     lsr.b    #2,d0            ;and eliminate 2 last right bits
  347.  
  348. jos2    move.l    (a1)+,(a2)+        ;copy necessary no. of longs
  349.     subq.b    #1,d0            ;no. of longs--
  350.     bne.b    jos2            ;loop
  351.     
  352.     and.b    d3,d6            ;store 2 right bits
  353.     beq.b    jos            ;if there is no chars, continue
  354.  
  355. x    move.b    (a1),(a2)+        ;copy char
  356.     move.b    (a1)+,d6        ;read next char
  357.     cmp.b    d4,d6            ;is it LINE FEED,
  358.     bne.b    x            ;no, copy more chars
  359.     bra.b    jos            ;yes, continue
  360.  
  361. ;***********************************************************************
  362. next    move.l    #izlaz,d1
  363.     move.l    #1006,d2
  364.     jsr    open(a5)        ;open output file
  365.     tst.l    d0
  366.     beq.w    error2            ;output file error
  367. ;-------------
  368.     move.l    d0,d1            ;file pointer
  369.     move.l    d0,-(a7)        ;store
  370.     move.l    dest,d2            ;address
  371.     move.l    length,d3        ;file length
  372.     jsr    write(a5)        ;write output file
  373. ;-------------
  374.     move.l    (a7)+,d1
  375.     jsr    close(a5)        ;close output file
  376. ;-------------
  377.     jsr    output(a5)
  378.     move.l    d0,d1
  379.     move.l    #done,d2        ;write last message
  380.     moveq    #$10,d3
  381.     jsr    write(a5)
  382.     
  383. dealloc    move.l    size,d0
  384.     move.l    source,a1
  385.     jsr    freemem(a6)        ;free 1st memory
  386. ;-------------
  387.     move.l    size,d0
  388.     move.l    dest,a1
  389.     jsr    freemem(a6)        ;free 2nd memory
  390. ;-------------
  391.     move.l    size2,d0
  392.     move.l    pointers1,a1
  393.     jsr    freemem(a6)        ;free place for pointers
  394. ;-------------
  395.     move.l    no_of_lines,d0
  396.     move.l    pointers2,a1        ;free place for line lengths
  397.     jsr    freemem(a6)
  398. ;-------------
  399. kraj2    move.l    a5,a1
  400.     jsr    closelibrary(a6)    ;close dos.library
  401.     movem.l    (a7)+,d1-d7/a1-a6
  402.     rts
  403. ;***********************************************************************
  404. kraj    bsr.b    ekran            ;pointer in d1
  405.     move.l    #logo,d2
  406.     move.l    #$ee,d3
  407.     jsr    write(a5)        ;write text message
  408.  
  409.     jmp    kraj2
  410.  
  411. error1    bsr.b    ekran
  412.     move.l    #greska1,d2
  413.     moveq    #22,d3
  414.     jsr    write(a5)        ;write text input error
  415.  
  416.     jmp    dealloc
  417.  
  418. error2    bsr.b    ekran
  419.     move.l    #greska2,d2
  420.     moveq    #22,d3
  421.     jsr    write(a5)        ;write text output error
  422.  
  423.     jmp    dealloc
  424.  
  425.  
  426. ekran    jsr    output(a5)
  427.     tst.l    d0
  428.     beq.b    .ekr2
  429.     move.l    d0,d1
  430.     rts
  431.  
  432. .ekr2    move.l    (a7)+,d0        ;return address pick from stack
  433.     jmp    dealloc
  434.  
  435. string    movem.l    d1-d3/a1,-(a7)        ;store regs
  436.  
  437.     moveq    #10,d1            ;LINE FEED
  438.     moveq    #32,d2            ;SPACE
  439.     clr.l    d0            ;clear counter
  440. .a    move.b    (a0),d3
  441.     cmp.b    d2,d3            ;is it SPACE
  442.     beq.s    .bb
  443.     cmp.b    d1,d3            ;is it LINE FEED
  444.     beq.b    .c
  445.     tst.l    d3            ;is it NULL
  446.     beq.b    .c
  447.     move.b    (a0)+,(a1)+        ;copy char
  448.     addq.l    #1,d0            ;counter++
  449.     bra.b    .a
  450. .bb    addq.l    #1,a0            ;address++
  451.     cmp.b    (a0),d2            ;is it another SPACE
  452.     beq.b    .bb            ;if not, stay here
  453. .c    clr.b    (a1)            ;put NULL at the end of string
  454.     addq.l    #1,d0            ;counter++
  455.     movem.l    (a7)+,d1-d3/a1        ;bring back regs
  456.     rts
  457.  
  458. ;------------------------------------------------------------------------------    
  459. doslib    dc.b    "dos.library",0
  460. ulaz    ds.b    40
  461. izlaz    ds.b    40
  462. buff    ds.b    40
  463. logo    dc.b    10,"Shellsort V1.12 ",10                ;18
  464.     dc.b    "   Made by ONE MAN GANG",10                ;24
  465.     dc.b    "Herendic Drazen",10                    ;16
  466.     dc.b    "26. lipanj 9",10,"43240 CAZMA",10,"CROATIA",10,10    ;34
  467.     dc.b    "USAGE: Shellsort [-n] input_file output_file ",10    ;46
  468.     dc.b    "  -n leading spaces and control characters are ignored",10,0 ;56
  469.     dc.b    "     (tabs, line feeds, form feeds, etc.)",10,10,0    ;44
  470. ;         1---5----0----5----0----5----0----5----0----5----0
  471. reading    dc.b    "Reading...",0,0
  472. sorting    dc.b    $9b,$31,$30,$44,"Sorting...",0,0
  473. writing    dc.b    $9b,$31,$30,$44,"Writing...",0,0
  474. done    dc.b    $9b,$31,$30,$44,"Done !    ",10,0
  475. greska1    dc.b    10,"Input file error ! ",10,0
  476. greska2    dc.b    10,"Output file error !",10,0
  477. dosbase    dc.l    0
  478. length    dc.l    0        ;length of file
  479. source    dc.l    0        ;address where file is loaded
  480. dest    dc.l    0        ;address where sorted file is stored
  481. pointers1    dc.l    0    ;array of pointers to start of line
  482. pointers2    dc.l    0    ;array of pointers on lengths of lines
  483. no_of_lines    dc.l    0    ;no. of lines=no. of pointers
  484. flag    dc.b    0,0        ;for option '-n'
  485. size    dc.l    0
  486. size2    dc.l    0
  487.